每一个人都应当了解的科学技术（Techniques Everyone Should Know）
由 Peter Bailis 介绍
被选中的读物
在这个篇章之中，我们将会就数据库系统设计当中主要的，以及近主要的核心概念的策源地文章进行介绍：查询规划，事务控制，数据库恢复，以及分布式。而本章当中所牵涉到的思想，几乎是每一款现代数据库系统的基础，而每一款成熟的数据库系统基本上都牵涉到了这些概念。本章当中所搜集的三篇参考文章都是他们所立足的各自领域的经典文章。除此之外，与（红皮书）前面的篇章不同，在本章里面，我们更倾向 于聚焦那些已经得到广泛应用的科学技术与程序算法，而非整个数据库系统。
查询优化（Query Optimization）
在关系型数据库领域里面，查询优化技术至关重要，它是实现独立于数据的查询处理的核心支撑（即查询效率的好坏与数据关联度小，译者注）。Selinger 等人围绕 System R 的研究而著成的奠基性文章，通过将查询优化这个大问题，划分为三个小问题：代价的估计（cost estimation），通过关系的等价性（relational equivalences）定义搜索空间，以及基于代价的搜索（cost-based search），来让查询优化落地生根。
优化器会为查询执行当中的所涉及到的每一个组件，提供对应的代价估计，其测量单位，使用I/O与CPU的代价（I/O and CPU costs）来进行表示。而为了顺利实现这一目的，优化器，一方面需要依靠由我们预先设计出的有关每条关系数据存储内容的统计信息（这些数据存储于系统目录，即 system catalog 中），而另一方面，（优化器）需要结合一组启发式方法，来决定查询输出的基数大小（比如，基于预估的谓词选择性（predicate selectivity））。而作为练习，我们可以对这些启发式的方法，做一个详细地考虑：究竟何时，使用他们才算明智？究竟何时，哪一种输入将会导致他们工作失误？又或者，他们如何才可以更好地展开工作？
依托这些代价估计参数，优化器使用动态编程算法为查询构建出对应的执行计划。优化器 ，将会定义出一组物理操作符，它们是对逻辑操作符的具体实现（比如，查找一则元组，就使用完整的“段”扫描，和索引来完成）。而依托于这组操作符集合，优化器即可以迭代地构造出一棵“左深”操作符树来，这棵树使用代价启发式策略让总体运行这些操作符的工作量，达到一个最低水平，进而兼顾上游消费者所需的“感兴趣的顺序”。
这种做法同样规避了在运算时需要计算出操作符全部排列组合顺序的需要。然而，在查询规划这件事情的开销上，它依旧是一个指数级别的操作。正如我们将在第七章讨论的情况那样，现代的查询优化器，依旧难以处理庞大的查询计划（比如，多路 join）。除此之外，即便 Selinger 等人的优化器，会在执行之前，做一个预编译的工作，但是其它很多早期的如Ingres[^25]那样的数据库系统，实际上依旧在逐个元组的基础上面展开工作。
就像几乎所有的查询优化器那样，Selinger 他们的查询优化器，实际上也不是“最优的” --- 它们并不保证由查询优化器最终所选择的查询计划，将会是最快速，或者是成本最廉价的。关系型数据库的查询优化器，从精神上面看，更加接近于现代语言编译器当中的代码优化例程（比如，将要执行尽力而为的搜索行为（best-effort search）），而并非数学意义上面的优化例程（比如，将要找出最优化的解决方案）。不过，如今许多关系型数据库引擎，都沿用了本文当中的方法，包括二进制操作符，以及基于代价的成本估计。
并发控制（Concurrency Control）
我们所选择第一篇事务方面的论文，出自 Gray 等研究人员之手。文章当中，介绍了两种经典思想：多重粒度锁定以及多元模式锁定。就实际来说，它理当被划分为两篇不同的文章。
首先，这篇论文抛出了多粒度锁定的概念。此处的问题实际上非常简单：给定一个具有层次机构的数据库，请问我们应当如何让他们执行互斥操作？还有，我们应当在什么时候，选择粗粒度的锁定方案（比如，为整个数据库加锁）或细粒度的锁定方案（比如，为单独的数据记录加锁）？以及，我们如何支持同时对层次结构中的不同部分展开同时访问？尽管 Gray 等人的分层结构（由数据库，区域，文件，索引，以及记录），同现代化的数据库相较差异并不大。除了最基本的之外，其它绝大多数的当代数据库基本上都适应了他们今天的这些建议。
第二，这篇文章，提出了多重隔离性的概念。正如 Gray 等人所提醒我们的那样，并发控制的目标，应当是保持数据的“一致性”，因为它遵循一定的逻辑断言。传统上而言，数据库系统，使用可串行化事务来保障数据的强一致性：如果每一个事务都让数据库处于“一致状态”，那么可串行化的执行（等价于一些序列化执行的事务）将会保证，所有的事务，都将会遵循数据库的“一致”状态[^5]。Gray 等人的“Degree”协议，就描述了经典的“两阶段加锁”（2PL）理论，它既保证了事务的可串行化执行，也是事务处理的主要概念之一。
不过，事务的可串行化执行总是被认为其实现代价过于昂贵，无法强制执行。而为了改善性能，数据库在执行事务的时候，总是会使用一些非可串行化的隔离级别。而在这里，持有锁，是一件非常昂贵的事情；而在存在冲突的情况下申请锁，其等待又将会耗费时间；而一旦牵涉到死锁，则可能会永远等待下去（或者造成程序的终止）。因此，早在1973年，类似于IMS和System R 这样的数据库管理系统，就开始在实验一些非可串行化的隔离性政策。在基于锁的事务控制系统里面，这些政策的实现方法，就是让持有锁的时间，更短一些，并由此保证更好的并发性，削减事务里面的死锁，以及系统内部引起的中止操作，同时，在分布式环境里面，它可以提高数据管理操作的可用性。
而在这篇文章的后半部分，Gray 等人提供了对于这些基于锁的加锁政策的初步形式化验证。截至目前，它们已经十分流行；而正如我们将在第六章中所讨论的事情那样，非可串行化的隔离性总是商用或者开源关系型数据库的默认事务隔离级别，且在某些关系型数据库系统中间，可串行化隔离级别，就根本不会被提供出来。第二层级在今天，被称作可重复读隔离级别，而第一层级，则被称为读已提交隔离级别，而层级0几乎已经绝迹[^27]。这篇论文同样对可恢复性这个重要的概念，展开了研究：在这种策略下面，在不影响其它事务的情况下，中止或者撤销事务的策略。除了层级0之外的其它层级，都可以满足这个属性。
而在 Gray 等人基于锁的可串行化开创性工作完成之后，很多可供选择的事务控制机制就被提了出来。而伴随着硬件，应用程序需求，以及访问模式的变化，并发控制子系统一样发生了改变。然而，并发控制里面的一个属性依旧保持着一个基本确定的事情：在并发访问控制之中，并不存在一种片面的“最佳”机制。最优的战略需要同工作负载结合的。为了点出这一点，我们已经将来自于 Agrawal,Carey, Livny 的研究涵盖进来。截至目前，这篇文章虽然已经过时，但是其中的方法，策略以及延伸出来的结论，依旧是准确的。这是一个经过深思熟虑且同实现无关的性能分析工作的良好案例，它能够随着时间的推移，为未来的我们，提供许多宝贵的经验教训。
从方法逻辑上面来看，拥有被称为“对于信封的回溯（back of the envelope，也就是使用简化逻辑来看待问题）”是一项非常有价值的技能：使用简单、粗略的计算指标，在合理的数量级之中，快速来做出一项估计，可以节省数个小时，乃至于数年的系统实现以及性能分析时间。在数据库系统之中，这是一项长期传承，且相当有用的传统，从“五分钟法则”[^4]到谷歌公司的“每一个人都应当了解的数字”[^10], [^8]。尽管在这些解读当中，得出的结论相当简单，但是它们给予了我们长期的启示。
不过，对于诸如并发控制这样的复杂系统的分析而言，模拟可能是介于“使用简化逻辑粗略估计问题”同全面完备的系统压测（full-blown systems benchmarking）间的一项有价值的中间步骤。Agrawal 的研究就是对于这种路径的一个案例：作者小心翼翼地用一款精心设计的系统与用户模型，模拟基于锁与基于重启的（restart-based）的乐观并发控制机制。
如下几个方面的评估尤其具有其价值。
首先，在几乎所有的图里面，都存在一个“交叉”点：在这个点，没有明确的最佳胜者（clear winner），因为好的解决方案总是会同系统配置与工作负载相结合。而与之相对的，那些不存在交叉点的研究报告，几乎总是令人不感兴趣。倘若一份模式“总是获胜”，那么这份研究，理当包含一份详尽的分析来，或者，请至少提供证据，说服我们，该结果为什么会在这份报告当中得出来。
第二，作者对广泛的系统配置参数进行了思考；对在模型里面的几乎每一个参数，都展开了研究和讨论。
第三，许多图都表现出了非单调性的特征（并不会总是向上或者向右），这是反复折腾（thrashing）与资源受限的产物。正如作者的所述，对资源的无限性假设将会导致截然不同的结果。而一个缺少了点谨慎心的模型，假如暗含这一假设，其实用性将会大打折扣。
最后，这个研究的结论非常合理。基于重启的工作策略，其主要成本就体现于发生冲突时的资源浪费之上。当资源充足之时，投机取巧有其意义所在：因为消耗的资源成本，会降低许多，且在无限资源这一背景之下，它的开销可以忽略不计（it is free）。然而，在资源受限之时，阻塞战略将是一种开源节流，优化性能的更优方案。因此，普遍的单方面适用方案，并不存在。然而，该论文的假定，依旧是有先见之明，因为计算资源依旧稀缺。就实际而看，到了今天，很少有商业系统，依旧采取基于重启的方法策略。不过，随着技术比例 -- 磁盘，网络，CPU 速率 -- 的不断调整，重新对这种权衡展开审视，依旧有其意义。
数据库的恢复（Database Recovery）
另外一个主要挑战在于，事务处理需要维持数据的持久性：事务处理应当可以经受住系统故障的影响。而最近的一些技术就是依托日志机制维系数据持久性：在事务的执行期间，事务的操作，将会以 日志的形式，保存于那些可以容忍失败的存储介质上面（比如，硬盘或者SSD）。而每一个数据库领域的工作者，都应当理解预先写入式（wal）日志的工作方法，最好能够深入了解其细节。
能够实现“没有强求，偷窃”（“No Force，Steal”）的基于wal日志的恢复管理器的候选算法，就是IBM的ARIES算法，它也是我们选择的下一篇论文的主题。（资深的数据库研究者，可能会告诉 Tandem 与 Oracle 几乎同时提出了类似的设想）。在 ARIES 之中，数据库并不需要在提交的时候，就将脏页写入磁盘（“No Force”），而可以在任何时候，就将脏页写入于磁盘上面（“Steal”）[^78];这些工作策略性能表现良好，目前已在绝大多数的商业数据库中，得到良好应用，不过，它也为数据库增添了复杂性。
ARIES 的基本思想是分三个阶段，完成故障恢复工作。
第一步，ARIES 将通过向前日志回放，来判断数据库崩溃发生时，正在处理中的事务，即分析阶段（analysis phase）。
第二步，ARIES 将会再次回放日志，将崩溃发生时，正在处理的那些事务的数据变化落实落地，即重做阶段（redo stage）。
第三步，ARIES 将会向后回滚日志，消除崩溃发生时，未能提交的事务的影响，即撤销阶段（undo stage）。
因此，ARIES 的核心思想就是在“重复历史”中执行恢复。实际上，撤销阶段同日常操作中的终止事务操作，遵循的是一个逻辑。
从理论上看，ARIES 应当是一篇非常简单的论文，但是实际来说，它其实是我们所搜集的这组文章中，复杂程度达到最深的文章。
在研究生阶段的课程之中，这篇文章作为成人礼（rite of passage）而存在。不过，因为这篇材料非常基础，所以理解它，是一件重要的事情。幸运的是，Ramakrishnan 与 Gahrke 的尚未出版的数据库教材[^127]，以及由 Michael Franklin 所提供的研究报告，都给出了 ARIES 的通俗版本。而我们在这里所包含的完整ARIES文章，明显要复杂的多，这是因为它对故障恢复可替代（replay-redo-undo）设计方案缺陷的转移性讨论。因此，如果你是第一次尝试对于数据库领域展开学习，我们非常鼓励读者，忽略这篇材料，仅仅关注 ARIES 的实现策略。而那些替代方案的缺点与不足，固然重要，但是我们还是应当在第二次，或者是第三次阅读文章的时候，对其做深入的理解。而除了文章的组织结构之外，ARIES 对于诸如索引这样的数据库内部组件（比如，嵌套顶部操作（nested top actions）与逻辑上面的 undo 日志记录 -- 后者，往往被应用于诸如 Escrow 事务[^124]这样的具有鲜明特色的模式之中），和最小化数据库崩溃时间技术的讨论，也使得文章的复杂性，提升明显。而从现实中看，尽可能缩短恢复时间是非常重要，但是很难实现。
分布式
我们最后选中的这篇文章，着重关注在分布式环境下面的事务执行。这个主题在今天的世界已经变得尤为重要，越来越多的分布式数据库正在诞生 --- 他们要么具备良好的复制能力，能够将同一份数据，拷贝形成多个副本，放到不同的服务器上面；要么具备分区性，其数据项分别（或者同时）存储于毫不相关的服务器上面。而在可靠性，持续性，可用性之外，分布式为数据库领域，引入很多崭新理念。服务端可能会出现工作故障，而网络连接则可能变得不可靠。而即使没有任何故障，网络间数据传输，其开销也可能非常昂贵。
不过现在，让我们把目光聚焦于分布式事务处理的一项核心科技上面：原子化提交（atomic commitment, ac）。用非常不正式的说法来看，对于一项给定的，需要在多台服务器（要么是多个副本，要么是多个分区，或者两者兼具），AC 将会保证所有的事务，要么全部提交，要么全部终止。
实现 AC 的经典算法，大约在 1970 年代中期提出，被称呼为“两阶段提交”（Two-Phase Commit，2PC，注意，千万不要把它同 Two-Phase Locking，2PL 混淆起来）[^67]，[^100]，同时，为了提供对于两阶段提交和 wal 日志与提交协议之间交互方法的良好回顾，我们在这里所参考的文章，同时包含了两种对于 AC 的变体实现方案，他们都对性能，做出来了一定的改进。对于推测终止(The Presumed Abort)这一种变体实现方案，他们可以使得工作中的进程，能够规避将终止操作应用到磁盘和获取操作的终止，进而促成磁盘利用率和网络阻塞的削减。而对于假定提交优化（The Presumed Commit）这种变式方案而言，其情况总是类似的，他们在面对更多地的事务提交的时候，同样可以对空间的利用，以及网络的阻塞，做出一定的优化。此处的难点，着重反映在两阶段提交中，各个对象的交互，比如本地的存储（local storage），本地的事务管理（the local transaction manager）;这些事情的细节是如此重要，以至于正确地实现这些协议，可以成为一件非常具有挑战性的事情。
故障的可能性使得 AC 变得复杂（这也是分布式计算环境下面的最主要问题）。举例来说，在 2PC 之下，如果协调节点与参与节点，在所有的参与节点已经完成投票之后，而协调节点尚未收到参与节点失败消息就出现故障的时候，会发生什么？剩余的参与节点 将会陷入茫然，因为它们并不清楚，究竟应当提交事务，还是要选择终止事务：发送失败信号的参与节点，究竟是选择了YES，或者是投出了NO?由此使得，参与者节点，将不再能够继续顺利地推进工作。而实际上，所有对于 AC 的实现方案，在不可靠的网络环境上展开工作的时候，都难免遭遇阻塞，或者毫无进展的问题。再考虑到可串行化并发控制，阻塞 AC 可能意味着吞吐量陷入停滞之中。因此，许多有关的AC算法在宽松的网络环境假定下（比如，假定网络环境是同步网络（synchronous network））以及良好的服务器信息可用性（比如，充分利用好“故障检测器”，判断哪一个节点发生了故障）检查了AC[^14]。
最后，许多读者可能相当熟悉与一致性相关的那些问题，亦或是，可能对诸如 Paxos 算法这一类的一致性算法实现方案有过一定了解。在一致性问题这个领域上面，只要在最终，所有的参与进程，能够达成共识，那么任何的提议，都是可以被接受的。（相对的，在 AC 中，所有的独立参与节点可以投NO，而由此就会使得所有的参与者，被强制终止）。而这种特性，也就使得，达成共识，相较于 AC，是一个更为容易的问题[^75]，但是，对于 AC 而言，任何对于一致性的实现，在特定的场合之中，也容易引发阻塞的情况[^60]。在现代化的分布式数据库之中，一致性，总是被应用称为复制的基础，以此来确保复制节点的更新能够按照同样的顺序被落地起来，而对于那些状态机模型下面的复制（请参考 Schneider 的训练教程[^141]）。AC总是被应用于执行那些可以跨越多个分区的事务。由 Lamport[^99]所提出来的 Paxos 算法，是最早的（也是最著名的，因为它的复杂程度，同ARIES不相上下）对于一致性的实现方案。不过，基于视图的复制（Viewstamped Replication）[^102]，Raft[^125]，ZAB[^92]，以及 Multi-Paxos[^35]算法可能可以在实践中，起到更好的帮助作用。这是因为，这些算法的实现，都实现了对于分布式日志的抽象（而在原始的 Paxos 文章中，这被称为“一致性对象”）
不幸的事情在于，数据库社区与分布式计算社区间的交流，在某种程度上，相互割裂。尽管它们在数据的复制这一领域上，存在着共同的兴趣点，但是多年来，两个社区的观点交流，依旧是十分有限。在云计算以及可伸缩互联网的数据管理领域，这种割裂的情况，由所好转。比如，Gray 与 Lamport 在 Paxos Commit[^71]这个领域上面，于2006年展开了合作，这是一种结合了 AC 和 Lamport 的 Paxos 的算法。同时在这个结合点上面，尽管依旧还有很多工作需要开展，但是，“每一个人都应当了解的科技”的数量正在增加。
References
[1] H. Berenson, P. Bernstein, J. Gray, J. Melton, E. O’Neil, and P. O’Neil. A critique of ANSI SQL isolation levels. In
SIGMOD, 1995.
[2] P. Bernstein, V. Hadzilacos, and N. Goodman. Concurrency control and recovery in database systems, volume 370.
Addison-Wesley New York, 1987.
[3] T. D. Chandra, R. Griesemer, and J. Redstone. Paxos made live: an engineering perspective. In PODC, 2007.
[4] J. Dean. Designs, lessons and advice from building large distributed systems (keynote). In LADIS, 2009.
[5] K. P. Eswaran, J. N. Gray, R. A. Lorie, and I. L. Traiger. The notions of consistency and predicate locks in a database
system. Communications of the ACM, 19(11):624–633, 1976.
[6] M. J. Fischer, N. A. Lynch, and M. S. Paterson. Impossibility of distributed consensus with one faulty process. Journal
of the ACM (JACM), 32(2):374–382, 1985.
[7] M. J. Franklin. Concurrency control and recovery. The Computer Science and Engineering Handbook, pages 1–58–1077,
1997.
[8] G. Graefe. The five-minute rule twenty years later, and how flash memory changes the rules. In DaMoN, 2007.
[9] J. Gray. Notes on data base operating systems. In Operating Systems: An Advanced Course, volume 60 of Lecture Notes
in Computer Science, pages 393–481. Springer Berlin Heidelberg, 1978.
[10] J. Gray and G. Graefe. The five-minute rule ten years later, and other computer storage rules of thumb. ACM SIGMOD
Record, 26(4):63–68, 1997.
[11] J. Gray and L. Lamport. Consensus on transaction commit. ACM Transactions on Database Systems (TODS), 31(1):133–
160, Mar. 2006.
[12] J. Gray and F. Putzolu. The 5 minute rule for trading memory for disc accesses and the 10 byte rule for trading memory
for cpu time. In SIGMOD, 1987.
[13] R. Guerraoui. Revisiting the relationship between non-blocking atomic commitment and consensus. In WDAG, 1995.
[14] R. Guerraoui, M. Larrea, and A. Schiper. Non blocking atomic commitment with an unreliable failure detector. In SRDS,
1995.
[15] T. Haerder and A. Reuter. Principles of transaction-oriented database recovery. ACM Computing Surveys (CSUR),
15(4):287–317, 1983.
[16] F. P. Junqueira, B. C. Reed, and M. Serafini. Zab: High-performance broadcast for primary-backup systems. In DSN,
2011.
[17] L. Lamport. The part-time parliament. ACM Transactions on Computer Systems (TOCS), 16(2):133–169, 1998.
[18] B. Lampson and H. Sturgis. Crash recovery in a distributed data storage system. Technical report, 1979.
[19] B. Liskov and J. Cowling. Viewstamped replication revisited. Technical report, MIT, 2012.
[20] P. E. O’Neil. The escrow transactional method. ACM Transactions on Database Systems, 11(4):405–430, 1986.
[21] D. Ongaro and J. Ousterhout. In search of an understandable consensus algorithm. In USENIX ATC, 2014.
[22] R. Ramakrishnan and J. Gehrke. Database management systems. McGraw Hill, 2000.
[23] F. B. Schneider. Implementing fault-tolerant services using the state machine approach: A tutorial. ACM Computing
Surveys (CSUR), 22(4):299–319, 1990.
[24] D. Skeen. Nonblocking commit protocols. In SIGMOD, 1981.
[25] M. Stonebraker, G. Held, E. Won由 Peter Bailis 介绍
被选中的读物
Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price. Access path selection in a relational database management system. SIGMOD, 1979.
C. Mohan, Donald J. Haderle, Bruce G. Lindsay, Hamid Pirahesh, Peter M. Schwarz. ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging. ACM Transactions on Database Systems, 17(1), 1992, 94-162.
Jim Gray, Raymond A. Lorie, Gianfranco R. Putzolu, Irving L. Traiger. Granularity of Locks and Degrees of Consistency in a Shared Data Base. , IBM, September, 1975.
Rakesh Agrawal, Michael J. Carey, Miron Livny. Concurrency Control Performance Modeling: Alternatives and Implications. ACM Transactions on Database Systems, 12(4), 1987, 609-654.
C. Mohan, Bruce G. Lindsay, Ron Obermarck. Transaction Management in the R* Distributed Database Man- agement System. ACM Transactions on Database Systems, 11(4), 1986, 378-396.
在这个篇章之中，我们将会就数据库系统设计当中主要的，以及近主要的核心概念的策源地文章进行介绍：查询规划，事务控制，数据库恢复，以及分布式。而本章当中所牵涉到的思想，几乎是每一款现代数据库系统的基础，而每一款成熟的数据库系统基本上都牵涉到了这些概念。本章当中所搜集的三篇参考文章都是他们所立足的各自领域的经典文章。除此之外，与（红皮书）前面的篇章不同，在本章里面，我们更倾向于聚焦那些已经得到广泛应用的科学技术与程序算法，而非整个数据库系统。
查询优化（Query Optimization）
在关系型数据库领域里面，查询优化技术至关重要，它是实现独立于数据的查询处理的核心支撑（即查询效率的好坏与数据关联度小，译者注）。Selinger 等人围绕 System R 的研究而著成的奠基性文章，通过将查询优化这个大问题，划分为三个小问题：代价的估计（cost estimation），通过关系的等价性（relational equivalences）定义搜索空间，以及基于代价的搜索（cost-based search），来让查询优化落地生根。
优化器会为查询执行当中的所涉及到的每一个组件，提供对应的代价估计，其测量单位，使用I/O与CPU的代价（I/O and CPU costs）来进行表示。而为了顺利实现这一目的，优化器，一方面需要依靠由我们预先设计出的有关每条关系数据存储内容的统计信息（这些数据存储于系统目录，即 system catalog 中），而另一方面，（优化器）需要结合一组启发式方法，来决定查询输出的基数大小（比如，基于预估的谓词选择性（predicate selectivity））。而作为练习，我们可以对这些启发式的方法，做一个详细地考虑：究竟何时，使用他们才算明智？究竟何时，哪一种输入将会导致他们工作失误？又或者，他们如何才可以更好地展开工作？
依托这些代价估计参数，优化器使用动态编程算法为查询构建出对应的执行计划。优化器，将会定义出一组物理操作符，它们是对逻辑操作符的具体实现（比如，查找一则元组，就使用完整的“段”扫描，和索引来完成）。而依托于这组操作符集合，优化器即可以迭代地构造出一棵“左深”操作符树来，这棵树使用代价启发式策略让总体运行这些操作符的工作量，达到一个最低水平，进而兼顾上游消费者所需的“感兴趣的顺序”。
这种做法同样规避了在运算时需要计算出操作符全部排列组合顺序的需要。然而，在查询规划这件事情的开销上，它依旧是一个指数级别的操作。正如我们将在第七章讨论的情况那样，现代的查询优化器，依旧难以处理庞大的查询计划（比如，多路 join）。除此之外，即便 Selinger 等人的优化器，会在执行之前，做一个预编译的工作，但是其它很多早期的如Ingres[^25]那样的数据库系统，实际上依旧在逐个元组的基础上面展开工作。
就像几乎所有的查询优化器那样，Selinger 他们的查询优化器，实际上也不是“最优的” --- 它们并不保证由查询优化器最终所选择的查询计划，将会是最快速，或者是成本最廉价的。关系型数据库的查询优化器，从精神上面看，更加接近于现代语言编译器当中的代码优化例程（比如，将要执行尽力而为的搜索行为（best-effort search） ），而并非数学意义上面的优化例程（比如，将要找出最优化的解决方案）。不过，如今许多关系型数据库引擎，都沿用了本文当中的方法，包括二进制操作符，以及基于代价的成本估计。
并发控制（Concurrency Control）
我们所选择第一篇事务方面的论文，出自 Gray 等研究人员之手。文章当中，介绍了两种经典思想：多重粒度锁定以及多元模式锁定。就实际来说，它理当被划分为两篇不同的文章。
首先，这篇论文抛出了多粒度锁定的概念。此处的问题实际上非常简单：给定一个具有层次机构的数据库，请问我们应当如何让他们执行互斥操作？还有，我们应当在什么时候，选择粗粒度的锁定方案（比如，为整个数据库加锁）或细粒度的锁定方案（比如，为单独的数据记录加锁）？以及，我们如何支持同时对层次结构中的不同部分展开同时访问？尽管 Gray 等人的分层结构（由数据库，区域，文件，索引，以及记录），同现代化的数据库相较差异并不大。除了最基本的之外，其它绝大多数的当代数据库基本上都适应了他们今天的这些建议。
第二，这篇文章，提出了多重隔离性的概念。正如 Gray 等人所提醒我们的那样，并发控制的目标，应当是保持数据的“一致性”，因为它遵循一定的逻辑断言。传统上而言，数据库系统，使用可串行化事务来保障数据的强一致性：如果每一个事务都让数据库处于“一致状态”，那么可串行化的执行（等价于一些序列化执行的事务）将会保证，所有的事务，都将会遵循数据库的“一致”状态[^5]。Gray 等人的“Degree”协议，就描述了经典的“两阶段加锁”（2PL）理论，它既保证了事务的可串行化执行，也是事务处理的主要概念之一。
不过，事务的可串行化执行总是被认为其实现代价过于昂贵，无法强制执行。而为了改善性能，数据库在执行事务的时候，总是会使用一些非可串行化的隔离级别。而在这里，持有锁，是一件非常昂贵的事情；而在存在冲突的情况下申请锁，其等待又将会耗费时间；而一旦牵涉到死锁，则可能会永远等待下去（或者造成程序的终止）。因此，早在1973年，类似于IMS和System R 这样的数据库管理系统，就开始在实验一些非可串行化的隔离性政策。在基于锁的事务控制系统里面，这些政策的实现方法，就是让持有锁的时间，更短一些，并由此保证更好的并发性，削减事务里面的死锁，以及系统内部引起的中止操作，同时，在分布式环境里面，它可以提高数据管理操作的可用性。
而在这篇文章的后半部分，Gray 等人提供了对于这些基于锁的加锁政策的初步形式化验证。截至目前，它们已经十分流行；而正如我们将在第六章中所讨论的事情那样，非可串行化的隔离性总是商用或者开源关系型数据库的默认事务隔离级别，且在某些关系型数据库系统中间，可串行化隔离级别，就根本不会被提供出来。第二层级在今天，被称作可重复读隔离级别，而第一层级，则被称为读已提交隔离级别，而层级0几乎已经绝迹[^27]。这篇论文同样对可恢复性这个重要的概念，展开了研究：在这种策略下面，在不影响其它事务的情况下，中止或者撤销事务的策略。除了层级0之外的其它层级，都可以满足这个属性。
而在 Gray 等人基于锁的可串行化开创性工作完成之后，很多可供选择的事务控制机制就被提了出来。而伴随着硬件，应用程序需求，以及访问模式的变化，并发控制子系统一样发生了改变。然而，并发控制里面的一个属性依旧保持着一个基本确定的事情：在并发访问控制之中，并不存在一种片面的“最佳”机制。最优的战略需要同工作负载结合的。为了点出这一点，我们已经将来自于 Agrawal,Carey, Livny 的研究涵盖进来。截至目前，这篇文章虽然已经过时，但是其中的方法，策略以及延伸出来的结论，依旧是准确的。这是一个经过深思熟虑且同实现无关的性能分析工作的良好案例，它能够随着时间的推移，为未来的我们，提供许多宝贵的经验教训。
从方法逻辑上面来看，拥有被称为“对于信封的回溯（back of the envelope，也就是使用简化逻辑来看待问题）”是一项非常有价值的技能：使用简单、粗略的计算指标，在合理的数量级之中，快速来做出一项估计，可以节省数个小时，乃至于数年的系统实现以及性能分析时间。在数据库系统之中，这是一项长期传承，且相当有用的传统，从“五分钟法则”[^4]到谷歌公司的“每一个人都应当了解的数字”[^10], [^8]。尽管在这些解读当中，得出的结论相当简单，但是它们给予了我们长期的启示。
不过，对于诸如并发控制这样的复杂系统的分析而言，模拟可能是介于“使用简化逻辑粗略估计问题”同全面完备的系统压测（full-blown systems benchmarking）间的一项有价值的中间步骤。Agrawal 的研究就是对于这种路径的一个案例：作者小心翼翼地用一款精心设计的系统与用户模型，模拟基于锁与基于重启的（restart-based）的乐观并发控制机制。
如下几个方面 的评估尤其具有其价值。
首先，在几乎所有的图里面，都存在一个“交叉”点：在这个点，没有明确的最佳胜者（clear winner），因为好的解决方案总是会同系统配置与工作负载相结合。而与之相对的，那些不存在交叉点的研究报告，几乎总是令人不感兴趣。倘若一份模式“总是获胜”，那么这份研究，理当包含一份详尽的分析来，或者，请至少提供证据，说服我们，该结果为什么会在这份报告当中得出来。
第二，作者对广泛的系统配置参数进行了思考；对在模型里面的几乎每一个参数，都展开了研究和讨论。
第三，许多图都表现出了非单调性的特征（并不会总是向上或者向右），这是反复折腾（thrashing）与资源受限的产物。正如作者的所述，对资源的无限性假设将会导致截然不同的结果。而一个缺少了点谨慎心的模型，假如暗含这一假设，其实用性将会大打折扣。
最后，这个研究的结论非常合理。基于重启的工作策略，其主要成本就体现于发生冲突时的资源浪费之上。当资源充足之时，投机取巧有其意义所在：因为消耗的资源成本，会降低许多，且在无限资源这一背景之下，它的开销可以忽略不计（it is free）。然而，在资源受限之时，阻塞战略将是一种开源节流，优化性能的更优方案。因此，普遍的单方面适用方案，并不存在。然而，该论文的假定，依旧是有先见之明，因为计算资源依旧稀缺。就实际而看，到了今天，很少有商业系统，依旧采取基于重启的方法策略。不过，随着技术比例 -- 磁盘，网络，CPU 速率 -- 的不断调整，重新对这种权衡展开审视，依旧有其意义。
数据库的恢复（Database Recovery）
另外一个主要挑战在于，事务处理需要维持数据的持久性：事务处理应当可以经受住系统故障的影响。而最近的一些技术就是依托日志机制维系数据持久性：在事务的执行期间，事务的操作，将会以日志的形式，保存于那些可以容忍失败的存储介质上面（比如，硬盘或者SSD）。而每一个数据库领域的工作者，都应当理解预先写入式（wal）日志的工作方法，最好能够深入了解其细节。
能够实现“没有强求，偷窃”（“No Force，Steal”）的基于wal日志的恢复管理器的候选算法，就是IBM的ARIES算法，它也是我们选择的下一篇论文的主题。（资深的数据库研究者，可能会告诉 Tandem 与 Oracle 几乎同时提出了类似的设想）。在 ARIES 之中，数据库并不需要在提交的时候，就将脏页写入磁盘（“No Force”），而可以在任何时候，就将脏页写入于磁盘上面（“Steal”）[^78];这些工作策略性能表现良好，目前已在绝大多数的商业数据库中，得到良好应用，不过，它也为数据库增添了复杂性。
ARIES 的基本思想是分三个阶段，完成故障恢复工作。
第一步，ARIES 将通过向前日志回放，来判断数据库崩溃发生时，正在处理中的事务，即分析阶段（analysis phase）。
第二步，ARIES 将会再次回放日志，将崩溃发生时，正在处理的那些事务的数据变化落实落地，即重做阶段（redo stage）。
第三步，ARIES 将会向后回滚日志，消除崩溃发生时，未能提交的事务的影响，即撤销阶段（undo stage）。
因此，ARIES 的核心思想就是在“重复历史”中执行恢复。实际上，撤销阶段同日常操作中的终止事务操作，遵循的是一个逻辑。
从理论上看，ARIES 应当是一篇非常简单的论文，但是实际来说，它其实是我们所搜集的这组文章中，复杂程度达到最深的文章。
在研究生阶段的课程之中，这篇文章作为成人礼（rite of passage）而存在。不过，因为这篇材料非常基础，所以理解它，是一件重要的事情。幸运的是，Ramakrishnan 与 Gahrke 的尚未出版的数据库教材[^127]，以及由 Michael Franklin 所提供的研究报告，都给出了 ARIES 的通俗版本。而我们在这里所包含的完整ARIES文章，明显要复杂的多，这是因为它对故障恢复可替代（replay-redo-undo）设计方案缺陷的转移性讨论。因此，如果你是第一次尝试对于数据库领域展开学习，我们非常鼓励读者，忽略这篇材料，仅仅关注 ARIES 的实现策略。而那些替代方案的缺点与不足，固然重要，但是我们还是应当在第二次，或者是第三次阅读文章的时候，对其做深入的理解。而除了文章的组织结构之外，ARIES 对于诸如索引这样的数据库内部组件（比如，嵌套顶部操作（nested top actions）与逻辑上面的 undo 日志记录 -- 后者，往往被应用于诸如 Escrow 事务[^124]这样的具有鲜明特色的模式之中），和最小化数据库崩溃时间技术的讨论，也使得文章的复杂性，提升明显。而从现实中看，尽可能缩短恢复时间是非常重要，但是很难实现。
分布式
我们最后选中的这篇文章，着重 关注在分布式环境下面的事务执行。这个主题在今天的世界已经变得尤为重要，越来越多的分布式数据库正在诞生 --- 他们要么具备良好的复制能力，能够将同一份数据，拷贝形成多个副本，放到不同的服务器上面；要么具备分区性，其数据项分别（或者同时）存储于毫不相关的服务器上面。而在可靠性，持续性，可用性之外，分布式为数据库领域，引入很多崭新理念。服务端可能会出现工作故障，而网络连接则可能变得不可靠。而即使没有任何故障，网络间数据传输，其开销也可能非常昂贵。
不过现在，让我们把目光聚焦于分布式事务处理的一项核心科技上面：原子化提交（atomic commitment, ac）。用非常不正式的说法来看，对于一项给定的，需要在多台服务器（要么是多个副本，要么是多个分区，或者两者兼具），AC 将会保证所有的事务，要么全部提交，要么全部终止。
实现 AC 的经典算法，大约在 1970 年代中期提出，被称呼为“两阶段提交”（Two-Phase Commit，2PC，注意，千万不要把它同 Two-Phase Locking，2PL 混淆起来）[^67]，[^100]，同时，为了提供对于两阶段提交和 wal 日志与提交协议之间交互方法的良好回顾，我们在这里所参考的文章，同时包含了两种对于 AC 的变体实现方案，他们都对性能，做出来了一定的改进。对于推测终止(The Presumed Abort)这一种变体实现方案，他们可以使得工作中的进程，能够规避将终止操作应用到磁盘和获取操作的终止，进而促成磁盘利用率和网络阻塞的削减。而对于假定提交优化（The Presumed Commit）这种变式方案而言，其情况总是类似的，他们在面对更多地的事务提交的时候，同样可以对空间的利用，以及网络的阻塞，做出一定的优化。此处的难点，着重反映在两阶段提交中，各个对象的交互，比如本地的存储（local storage），本地的事务管理（the local transaction manager）;这些事情的细节是如此重要，以至于正确地实现这些协议，可以成为一件非常具有挑战性的事情。
故障的可能性使得 AC 变得复杂（这也是分布式计算环境下面的最主要问题）。举例来说，在 2PC 之下，如果协调节点与参与节点，在所有的参与节点已经完成投票之后，而协调节点尚未收到参与节点失败消息就出现故障的时候，会发生什么？剩余的参与节点将会陷入茫然，因为它们并不清楚，究竟应当提交事务，还是要选择终止事务：发送失败信号的参与节点，究竟是选择了YES，或者是投出了NO?由此使得，参与者节点，将不再能够继续顺利地推进工作。而实际上，所有对于 AC 的实现方案，在不可靠的网络环境上展开工作的时候，都难免遭遇阻塞，或者毫无进展的问题。再考虑到可串行化并发控制，阻塞 AC 可能意味着吞吐量陷入停滞之中。因此，许多有关的AC算法在宽松的网络环境假定下（比如，假定网络环境是同步网络（synchronous network））以及良好的服务器信息可用性（比如，充分利用好“故障检测器”，判断哪一个节点发生了故障）检查了AC[^14]。
最后，许多读者可能相当熟悉与一致性相关的那些问题，亦或是，可能对诸如 Paxos 算法这一类的一致性算法实现方案有过一定了解。在一致性问题这个领域上面，只要在最终，所有的参与进程，能够达成共识，那么任何的提议，都是可以被接受的。（相对的，在 AC 中，所有的独立参与节点可以投NO，而由此就会使得所有的参与者，被强制终止）。而这种特性，也就使得，达成共识，相较于 AC，是一个更为容易的问题[^75]，但是，对于 AC 而言，任何对于一致性的实现，在特定的场合之中，也容 易引发阻塞的情况[^60]。在现代化的分布式数据库之中，一致性，总是被应用称为复制的基础，以此来确保复制节点的更新能够按照同样的顺序被落地起来，而对于那些状态机模型下面的复制（请参考 Schneider 的训练教程[^141]）。AC总是被应用于执行那些可以跨越多个分区的事务。由 Lamport[^99]所提出来的 Paxos 算法，是最早的（也是最著名的，因为它的复杂程度，同ARIES不相上下）对于一致性的实现方案。不过，基于视图的复制（Viewstamped Replication）[^102]，Raft[^125]，ZAB[^92]，以及 Multi-Paxos[^35]算法可能可以在实践中，起到更好的帮助作用。这是因为，这些算法的实现，都实现了对于分布式日志的抽象（而在原始的 Paxos 文章中，这被称为“一致性对象”）
不幸的事情在于，数据库社区与分布式计算社区间的交流，在某种程度上，相互割裂。尽管它们在数据的复制这一领域上，存在着共同的兴趣点，但是多年来，两个社区的观点交流，依旧是十分有限。在云计算以及可伸缩互联网的数据管理领域，这种割裂的情况，由所好转。比如，Gray 与 Lamport 在 Paxos Commit[^71]这个领域上面，于2006年展开了合作，这是一种结合了 AC 和 Lamport 的 Paxos 的算法。同时在这个结合点上面，尽管依旧还有很多工作需要开展，但是，“每一个人都应当了解的科技”的数量正在增加。
References
[1] H. Berenson, P. Bernstein, J. Gray, J. Melton, E. O’Neil, and P. O’Neil. A critique of ANSI SQL isolation levels. In
SIGMOD, 1995.
[2] P. Bernstein, V. Hadzilacos, and N. Goodman. Concurrency control and recovery in database systems, volume 370.
Addison-Wesley New York, 1987.
[3] T. D. Chandra, R. Griesemer, and J. Redstone. Paxos made live: an engineering perspective. In PODC, 2007.
[4] J. Dean. Designs, lessons and advice from building large distributed systems (keynote). In LADIS, 2009.
[5] K. P. Eswaran, J. N. Gray, R. A. Lorie, and I. L. Traiger. The notions of consistency and predicate locks in a database
system. Communications of the ACM, 19(11):624–633, 1976.
[6] M. J. Fischer, N. A. Lynch, and M. S. Paterson. Impossibility of distributed consensus with one faulty process. Journal
of the ACM (JACM), 32(2):374–382, 1985.
[7] M. J. Franklin. Concurrency control and recovery. The Computer Science and Engineering Handbook, pages 1–58–1077,
1997.
[8] G. Graefe. The five-minute rule twenty years later, and how flash memory changes the rules. In DaMoN, 2007.
[9] J. Gray. Notes on data base operating systems. In Operating Systems: An Advanced Course, volume 60 of Lecture Notes
in Computer Science, pages 393–481. Springer Berlin Heidelberg, 1978.
[10] J. Gray and G. Graefe. The five-minute rule ten years later, and other computer storage rules of thumb. ACM SIGMOD
Record, 26(4):63–68, 1997.
[11] J. Gray and L. Lamport. Consensus on transaction commit. ACM Transactions on Database Systems (TODS), 31(1):133–
160, Mar. 2006.
[12] J. Gray and F. Putzolu. The 5 minute rule for trading memory for disc accesses and the 10 byte rule for trading memory
for cpu time. In SIGMOD, 1987.
[13] R. Guerraoui. Revisiting the relationship between non-blocking atomic commitment and consensus. In WDAG, 1995.
[14] R. Guerraoui, M. Larrea, and A. Schiper. Non blocking atomic commitment with an unreliable failure detector. In SRDS,
1995.
[15] T. Haerder and A. Reuter. Principles of transaction-oriented database recovery. ACM Computing Surveys (CSUR),
15(4):287–317, 1983.
[16] F. P. Junqueira, B. C. Reed, and M. Serafini. Zab: High-performance broadcast for primary-backup systems. In DSN,
2011.
[17] L. Lamport. The part-time parliament. ACM Transactions on Computer Systems (TOCS), 16(2):133–169, 1998.
[18] B. Lampson and H. Sturgis. Crash recovery in a distributed data storage system. Technical report, 1979.
[19] B. Liskov and J. Cowling. Viewstamped replication revisited. Technical report, MIT, 2012.
[20] P. E. O’Neil. The escrow transactional method. ACM Transactions on Database Systems, 11(4):405–430, 1986.
[21] D. Ongaro and J. Ousterhout. In search of an understandable consensus algorithm. In USENIX ATC, 2014.
[22] R. Ramakrishnan and J. Gehrke. Database management systems. McGraw Hill, 2000.
[23] F. B. Schneider. Implementing fault-tolerant services using the state machine approach: A tutorial. ACM Computing
Surveys (CSUR), 22(4):299–319, 1990.
[24] D. Skeen. Nonblocking commit protocols. In SIGMOD, 1981.
[25] M. Stonebraker, G. Held, E. Wong, and P. Kreps. The design and implementation of ingres. ACM Transactions on
Database Systems (TODS), 1(3):189–222, 1976 g, and P. Kreps. The design and implementation of ingres. ACM Transactions on
Database Systems (TODS), 1(3):189–222, 1976